package com.ry.day1129;

//LC177 和这题答案差不多
public class LC106 {


      static class ListNode {
          int val;
          ListNode next;
          ListNode(int x) {
              val = x;
              next = null;
          }
      }


      static class TreeNode {
          public int val;
          public TreeNode left, right;
          public TreeNode(int val) {
              this.val = val;
              this.left = this.right = null;
          }
      }


    static class Solution {
        /**
         * @param head: The first node of linked list
         * @return: a tree node
         */
        public TreeNode sortedListToBST(ListNode head) {
            ListNode cur = head;
            int cnt = 0;
            while (cur!=null){
                cnt++;
                cur=cur.next;
            }

            int[] arr = new int[cnt];
            cur= head;
            int idx =0;
            while (cur!=null){
                arr[idx++] = cur.val;
                cur=cur.next;
            }

            return f(arr,0,cnt-1);
        }

        public TreeNode f(int[] arr,int left,int right){
            if(left>right) return null;
            if(left==right) return new TreeNode(arr[left]);
            int mid = left+(right-left)/2;
            TreeNode root = new TreeNode(arr[mid]);
            root.left= f(arr,left,mid-1);
            root.right = f(arr,mid+1,right);
            return root;
        }
    }
}


/*
LintCode-Logo
学习
刷题
内推
VIP
其他...
搜索题目、标签、题集
邀请有礼
中文
您上个月的个人报告已生成，点击查看
avatar
106 · 有序链表转换为二叉搜索树
算法
中等
通过率
34%

题目
题解32
笔记
讨论99+
排名
记录
描述
给出一个所有元素以升序排序的单链表，将它转换成一棵高度平衡的二叉搜索树

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


链表长度不超过
50000
50000。

样例
样例 1：

输入：

linked list = 1->2->3
输出：

  2
 / \
1   3
解释：

将链表转换成一棵高度平衡的二叉搜索树。

样例 2：

输入：

linked list = 2->3->6->7
输出：

   3
  / \
 2   6
      \
       7
解释：

可能有多个答案，您可以返回任何一个。

相关知识
学习《2024年6月北美大厂最新面试真题精讲》课程中的2.9Meta：最新面试精选005相关内容 ，了解更多相关知识！
标签
相关题目

177
把排序数组转换为高度最小的二叉搜索树
简单

378
将二叉树转换成双链表
中等

453
将二叉树拆成链表
简单
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
37/3050
已开启智能提示
发起考试
30 分 00 秒
12345678910111213141516171819202122232425262728293031
 *
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }

控制台
历史提交

 */
